package com.exercises;

import java.util.Arrays;
import java.util.TreeSet;

class Exercise1818 {
    public static void main(String[] args) {
        int[] a = {1, 10, 4, 4, 2, 7};
        int[] b = {9, 3, 5, 1, 7, 4};
        System.out.println(minAbsoluteSumDiff(a, b));
    }

    public static int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        final int MOD = (int) Math.pow(10, 9) + 7;
        int max = 0, sum = 0, length = nums1.length;
        int[] rec = new int[length];
        System.arraycopy(nums1, 0, rec, 0, length);
        Arrays.sort(rec);
        for (int i = 0; i < length; i++) {
            int a = nums1[i], b = nums2[i];
            int min = Math.abs(a - b);
            int j = binarySearch(rec, nums2[i]);
            if (j < length) {
                max = Math.max(max, min - (rec[j] - nums2[i]));
            }
            if (j > 0) {
                max = Math.max(max, min - (nums2[i] - rec[j - 1]));
            }
            sum = (sum + Math.abs(a - b)) % MOD;
        }
        return (sum - max + MOD) % MOD;
    }

    public static int binarySearch(int[] rec, int target) {
        int low = 0, high = rec.length - 1;
        if (rec[high] < target) {
            return high + 1;
        }
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (rec[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

}

